package com.fanshuai.algorithms.divide;

/**
 * 求x得N次方
 */
public class PowerN {
    /**
     * 求x得次方  分治法解决
     * @param a
     * @param n
     * @return
     */
    public static long powerN(long a, int n) {
        if (n == 1) {
            return a;
        }

        if (n % 2 == 0) {
            return powerN(a, n/2) * powerN(a, n/2);
        } else {
            return a * powerN(a, (n - 1)/2) * powerN(a, (n - 1)/2);
        }
    }

    public static void main(String[] args) {
        System.out.println(powerN(4, 4));
    }
}
